/**
 * 2016年12月28日
 */
package algorithm.CIG.binarytree;

/**
 * @author Alex
 *
 */
abstract class Node{
	public Node(int type) {
		this.type = type;
	}
	Node left;
	Node right;
	//0 for val node 1 for sym node;
	int type;
}
class ValNode extends Node{
	public ValNode(int type,int val) {
		super(type);
		this.val = val;
	}
	int val;
}
class SymNode extends Node{
	public SymNode(int type,String sym) {
		super(type);
		this.sym = sym;
	}
	String sym;
}
//表达式形成的树,计算其结果
public class CalcExpression {
	static Node gen(){
		Node n1 = new SymNode(1,"+");
		Node n2 = new SymNode(1, "*");
		Node n3 = new SymNode(1, "-");
		
		Node n4 = new ValNode(0, 4);
		Node n5 = new ValNode(0, 3);
		Node n6 = new SymNode(1, "/");
		
		Node n7 = new ValNode(0, 1);
		
		Node n8 = new ValNode(0,12);
		Node n9 = new ValNode(0,2);
		
		n6.left = n8;
		n6.right = n9;
		
		n1.left = n2;
		n1.right = n3;
		n2.left = n4;
		n2.right = n5;
		
		n3.left = n6;
		n3.right = n7;
		
		return n1;
	}
	public static void main(String args[]){
		Node root = gen();	
		System.out.println(eval(root));
	}
	public static int eval(Node root){
		if(root instanceof SymNode){
			SymNode sn = (SymNode)root;
			String sy = sn.sym;
			switch(sy){
				case "+":
					return eval(root.left) + eval(root.right);
	//				break;
				case "-":
					return eval(root.left) - eval(root.right);
	//				break;
				case "*":
					return eval(root.left) * eval(root.right);
	//				break;
				case "/":
					return eval(root.left) / eval(root.right);
				default:
					throw new RuntimeException("unknow symbol");
			}
		}else{
			return ((ValNode)root).val;
		}
	}
	
}
